package com.mzy.linear_struct.hot100.二叉树;

import javafx.geometry.Pos;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: mizy3
 * @Date: 2024/08/21/下午9:55
 * @Description:
 */
public class Pro98验证二叉搜索树 {
/*    public boolean isValidBST(TreeNode root) {

        List<Integer> ans =  new ArrayList<>();
        inorderBST(root, ans);
        for (int i = 1; i < ans.size(); i++) {
            if (ans.get(i - 1) > ans.get(i)) {
                return false;
            }
        }

        return true;
    }

    private void inorderBST(TreeNode root, List<Integer> ans) {
        if(root ==null){
            return;
        }
        inorderBST(root.left, ans);
        ans.add(root.val);
        inorderBST(root.right, ans);
    }*/

    public boolean isValidBST(TreeNode root) {
        if (root.left == null && root.right == null) {
            return true;
        }
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean dfs(TreeNode root, long left, long right) {
        if (root == null) {
            return true;
        }

        int x = root.val;
        return x > left && x < right && dfs(root.left, left, x) && dfs(root.right, x, right);
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(2, new TreeNode(1), new TreeNode(3));
        new Pro98验证二叉搜索树().isValidBST(treeNode);
    }
}
